class Solution1 {
    public int mincostTickets(int[] days, int[] costs) {
        // 7 天内有 >= 4 则7优惠
        // 30 天内有 >= 21
        int lastDay = days[days.length - 1];
        boolean[] isTravel = new boolean[lastDay + 1];
        int[] dp = new int[lastDay + 1];
        for (int d : days) {
            isTravel[d] = true;
        }
        for (int i = 1; i <= lastDay; i++) {
            if (!isTravel[i]) {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = Math.min(dp[i - 1] + costs[0],
                 Math.min(dp[Math.max(i - 7, 0)] + costs[1], dp[Math.max(i - 30, 0)] + costs[2]));
            }
        }
        return dp[lastDay];
    }
}